package com.topInterview;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 15:09
 */
public class Leecode53_MaxSubArrSum {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int cur = 0;
        for (int i = 1; i < nums.length; i++) {
            cur = cur + nums[i];
            max = Math.max(max, cur);

            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }


    /**
     * dp思想
     *
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            int p1 = nums[i];
            int p2 = dp[i - 1] + nums[i];

            dp[i] = Math.max(p1,p2);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
